/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/longest-common-subsequence
   @Language: C++
   @Datetime: 16-02-09 05:56
   */

// Method 1, Time O(n*m), Space O(n*m), Time 50ms
class Solution {
public:
	/**
	 * @param A: A string
	 * @param B: A string
	 * @return: The length of longest common subsequence of A and B
	 */
	int longestCommonSubsequence(string &A, string &B) {
		// write your code here
		int la=A.length(), lb=B.length();
		vector<vector<int> > dp(la+1,vector<int>(lb+1,0));
		for(int i=1; i<=la; ++i){
			for(int j=1; j<=lb; ++j){
				if (A[i-1]==B[j-1]) dp[i][j]=dp[i-1][j-1]+1;
				else dp[i][j]=max(dp[i][j-1],dp[i-1][j]);
			}
		}
		return dp[la][lb];
	}
};

// Method 2, Time O(n*m), Space O(m), Time 9ms
class Solution {
public:
	/**
	 * @param A: A string
	 * @param B: A string
	 * @return: The length of longest common subsequence of A and B
	 */
	int longestCommonSubsequence(string &A, string &B) {
		// write your code here
		int la=A.length(), lb=B.length();
		vector<vector<int> > dp(2,vector<int>(lb+1,0));
		for(int i=1; i<=la; ++i){
			for(int j=1; j<=lb; ++j){
				if(A[i-1]==B[j-1]) dp[i&1][j]=dp[(i-1)&1][j-1]+1;
				else dp[i&1][j]=max(dp[i&1][j-1],dp[(i-1)&1][j]);
			}
		}
		return max(dp[0][lb],dp[1][lb]);
	}
};
